//Casa@130908a
//fault simulator
#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<vector>
#include<bitset>
#include<algorithm>
//#include<regex>
#include<unordered_map>
#include<random>
#include<cstring>
#include<ctime>

using namespace std;
//
//#define __DEBUG__
#define VEC_NUM		64 
#define MAX_CELL_IN_NUM	8
#define MAX_CELL_NUM	50000
#define MAX_INPUT_NUM	400
#define MAX_OUTPUT_NUM	400
#define MAX_GATE_NUM	40000
#define MAX_DFF_NUM		4000
#define	MAX_NODE_OUT_NUM	64
#define	MAX_NODE_NUM	40000

//#define MAX_VEC_LENGTH 	4000


//regex
//#define REG_CELL "\\b\\w+(?=\\()"
//#define REG_CELL_OUT "[\\w_.]+(?=(\\s*=))"
//#define REG_CELL_IN "(?<=\\()[\\w_.]+"

//structs
enum cell_type{NOT,AND,OR,NAND,NOR,INPUT,OUTPUT,DFF,NONE};
struct cell
{
	cell_type type;
	int in[MAX_CELL_IN_NUM],num;
	int out;
};
struct node
{
#ifdef __DEBUG__
	string name;
#endif
	int in;
	int out[MAX_NODE_OUT_NUM],num;
};
class msg
{
	string data;
public:
	msg(const string & data)
	{
		this->data=data;
	}
	string what()
	{
		return data;
	}
};

//Global Variable
//cell

#ifdef __DEBUG__
char cell_name[][8]={"NOT","AND","OR","NAND","NOR","INPUT","OUTPUT","DFF","NONE"};
#endif
cell cells[MAX_CELL_NUM];
int cell_num;
//
int input[MAX_INPUT_NUM],input_num;
int output[MAX_OUTPUT_NUM],output_num;
int gate[MAX_GATE_NUM],gate_num;
int dff[MAX_DFF_NUM],dff_num;
//node
node nodes[MAX_NODE_NUM];
int node_num;
//vector v1 v2 v3 ...
bitset<VEC_NUM> vec[MAX_INPUT_NUM+MAX_DFF_NUM];
int vec_length;//vec_num*sizeof(int)=vector num
//node status
bitset<VEC_NUM> node_value[MAX_NODE_NUM];
char node_visited[MAX_NODE_NUM];//node visited
//response
bitset<VEC_NUM> res[MAX_OUTPUT_NUM+MAX_DFF_NUM];
int res_length;
void read(const string& name)
{
	//regex reg_cell(REG_CELL,regex::icase);
	//smatch result;
	cout<<"\n["<<name<<"]"<<endl;
	//initialization
	cell_num=0;
	input_num=0;
	output_num=0;
	dff_num=0;
	gate_num=0;
	node_num=0;
	ifstream in(name);
	if(!in)
		throw msg(name+":cannot open");
	string line,buffer;
	while(getline(in,line))
	{
		if(line.length()==0||line.at(0)=='#')
			continue;
		for(int i=0;i<line.length();i++)
			if(line[i]=='('||line[i]==')'||\
				line[i]==','||line[i]=='=')
				line[i]=' ';
		buffer+=line+'\n';
	}
	istringstream ins(buffer);
	vector<string> ss;
	string s,_s;
	//char _c[100];
	while(getline(ins,s))
		if(s.length()>1)
			{
			istringstream iss(s);
			while(iss>>_s)
				{
				//cout<<_c<<endl;
				ss.push_back(_s);
				}
			ss.push_back("");
			//cout<<ss.back()<<endl;
			}
			
	//while(ins>>s)
		//ss.push_back(s);
	//INPUT|OUTPUT|DFF|NOT|AND|OR|NAND|NOR
	unordered_map<string,cell_type> _m={{"INPUT",INPUT},{"OUTPUT",OUTPUT}\
		,{"DFF",DFF},{"NOT",NOT},{"AND",AND},{"OR",OR},{"NAND",NAND},{"NOR",NOR}};
	unordered_map<string,int> node_map;
	int num=0;
	auto mf=[&](const string& t){
		if(node_map.find(t)==node_map.end())
		{
			node_map[t]=num;
			#ifdef __DEBUG__
			nodes[num].name=t;
			#endif
			num++;
		}};

	for(int i=0;i<ss.size();i++)
	{
		//cout<<i<<endl;
		if(ss[i]=="")continue;
		auto it=_m.find(ss[i]);
		if(it==_m.end())
		{
			mf(ss[i]);
		}
		else
		{
			int k;
			//cout<<cell_name[it->second]<<endl;
			switch(it->second)
				{
		
					case INPUT:
						mf(ss[++i]);
						cells[cell_num].type=it->second;
						cells[cell_num].out=node_map[ss[i]];
						input[input_num++]=cell_num++;
						break;
					case OUTPUT:
						mf(ss[++i]);
						cells[cell_num].type=it->second;
						cells[cell_num].in[0]=node_map[ss[i]];
						output[output_num++]=cell_num++;
						break;
					case DFF:
						cells[cell_num].type=it->second;
						cells[cell_num].out=node_map[ss[i-1]];
						mf(ss[++i]);
						cells[cell_num].in[0]=node_map[ss[i]];						
						dff[dff_num++]=cell_num++;
						break;
					case NOT:
					case AND:
					case OR:
					case NAND:
					case NOR:
						cells[cell_num].type=it->second;
						cells[cell_num].out=node_map[ss[i-1]];
						for(k=0,i++;ss[i].length()!=0&&_m.find(ss[i])==_m.end();i++,k++)
							{
							//cout<<ss[i]<<endl;
							mf(ss[i]);
							cells[cell_num].in[k]=node_map[ss[i]];	
							}
						//i--;
						cells[cell_num].num=k;
						gate[gate_num++]=cell_num++;
						//cout<<"^1"<<endl;
						break;
					default:
						throw msg("The cell type dose not exsist");
												
				}//switch
				//cout<<"^2"<<endl;
		}
//cout<<"^3"<<endl;
	}//for
	//nodes
	node_num=node_map.size();
	//cout<<"node_num="<<node_num<<endl;
	for(int i=0;i<node_num;i++)
		nodes[i].num=0;
	for(int i=0;i<cell_num;i++)
		{
		int t;
		switch(cells[i].type)
			{
			case INPUT:
				nodes[cells[i].out].in=i;
				break;			
			case OUTPUT:
				t=cells[i].in[0];
				nodes[t].out[nodes[t].num++]=i;
				break;
			case DFF:
				nodes[cells[i].out].in=i;
				t=cells[i].in[0];
				nodes[t].out[nodes[t].num++]=i;
				break;
			case NOT:
			case AND:
			case OR:
			case NAND:
			case NOR:
				nodes[cells[i].out].in=i;
				for(int j=0;j<cells[i].num;j++)
					{
					t=cells[i].in[j];
					nodes[t].out[nodes[t].num++]=i;
					}
				break;					
			default:
				throw msg("The cell type dose not exsist");
			}
		}
	//print
	cout<<"cell_num:"<<cell_num<<endl;
	cout<<"[input|output|gate|dff]\t"<<input_num<<','\
		<<output_num<<','<<gate_num<<','<<dff_num<<endl;
	cout<<"node_num:"<<node_num<<endl;
	#ifdef __DEBUG__	
	for(int i=0;i<node_num;i++)
		{
		cout<<"["<<nodes[i].name<<"] in:"<<cell_name[cells[nodes[i].in].type]<<"\tout:";
		for(int j=0;j<nodes[i].num;j++)
			cout<<cell_name[cells[nodes[i].out[j]].type]<<" ";
		cout<<endl;
		}
	#endif

	in.close();
}

//vector generator
void vec_gen(int length)
{
vec_length=length;
mt19937 generator ; 
for(int i=0;i<length;i++)
	for(int j=0;j<VEC_NUM;j++)
		vec[i][j]=generator()&1;
#ifdef __DEBUG__
cout<<"\nThe random test vectors is:"<<endl;
for(int i=0;i<vec_length;i++)
	cout<<vec[i]<<endl;
#endif
}

//back track
void back_track(int p)
{
	if(node_visited[p])
		return;
	int g=nodes[p].in;
	//bitset<VEC_NUM> _b;
	switch(cells[g].type)
		{
		case NOT:
			back_track(cells[g].in[0]);
			node_value[p]=~node_value[cells[g].in[0]];
			break;
		case AND:
			back_track(cells[g].in[0]);
			node_value[p]=node_value[cells[g].in[0]];
			for(int i=1;i<cells[g].num;i++)
				{
				back_track(cells[g].in[i]);
				node_value[p]&=node_value[cells[g].in[i]];
				}
			break;
		case OR:
			back_track(cells[g].in[0]);
			node_value[p]=node_value[cells[g].in[0]];
			for(int i=1;i<cells[g].num;i++)
				{
				back_track(cells[g].in[i]);
				node_value[p]|=node_value[cells[g].in[i]];
				}
			break;
		case NAND:
			back_track(cells[g].in[0]);
			node_value[p]=node_value[cells[g].in[0]];
			for(int i=1;i<cells[g].num;i++)
				{
				back_track(cells[g].in[i]);
				node_value[p]&=node_value[cells[g].in[i]];
				}
			node_value[p]=~node_value[p];
			break;
		case NOR:
			back_track(cells[g].in[0]);
			node_value[p]=node_value[cells[g].in[0]];
			for(int i=1;i<cells[g].num;i++)
				{
				back_track(cells[g].in[i]);
				node_value[p]|=node_value[cells[g].in[i]];
				}
			node_value[p]=~node_value[p];
			break;
		default:
			//cout<<g<<endl;
			//cout<<(int)node_visited[g]<<endl;
			//for(int i=0;i<dff_num;i++)
				//if(dff[i]==g)cout<<"find"<<endl;
			throw msg("invalid gate");
		}
	node_visited[p]=1;
}
//
//vector=input+dff
void initialization(const string& name)
{
	//get circute data
	read(name);
	//generate random vectors
	vec_gen(input_num+dff_num);
}

//get the value of all nodes based on the vector strored in vec.
//if node_pos>=0,the nodes[node_pos] stuck-at-value
void simulate(int node_pos=-1,bitset<VEC_NUM> value=bitset<VEC_NUM>(0))
{
	//apply vector
	memset(node_visited,0,sizeof(node_visited));
	for(int i=0;i<input_num;i++)
	{
		node_value[cells[input[i]].out]=vec[i];
		node_visited[cells[input[i]].out]=1;
	}
	for(int i=0;i<dff_num;i++)
	{
		node_value[cells[dff[i]].out]=vec[input_num+i];
		node_visited[cells[dff[i]].out]=1;
	}
	//insert stuck at fault
	if(node_pos>=0)
		{
		node_value[node_pos]=value;
		node_visited[node_pos]=1;
		}
	
	//get the value : output+dff
	for(int i=0;i<output_num;i++)
	{
		back_track(cells[output[i]].in[0]);
	}
	for(int i=0;i<dff_num;i++)
	{
		back_track(cells[dff[i]].in[0]);
	}
	//response vector
	res_length=0;
	for(int i=0;i<output_num;i++)
		res[res_length++]=node_value[cells[output[i]].in[0]];
	for(int i=0;i<dff_num;i++)
		res[res_length++]=node_value[cells[dff[i]].in[0]];
	//print
	#ifdef __DEBUG__
	cout<<"---\n";
	if(node_pos>=0)
		cout<<"FAULT:"<<nodes[node_pos].name<<endl;
	cout<<"The response is:"<<endl;
	for(int i=0;i<res_length;i++)
		cout<<res[i]<<endl;
	#endif
}

//statistic(detected fault number)
//-----PO(output)--PPO(DFF)---
//GATE   --------------------
//DFF     --------------------

//vec_num,res_num
int detectd[MAX_GATE_NUM+MAX_DFF_NUM][1+MAX_DFF_NUM];
//output response
bitset<VEC_NUM> output_res[MAX_OUTPUT_NUM];
//backup good state
//node status
bitset<VEC_NUM> good_node_value[MAX_NODE_NUM];
//response
bitset<VEC_NUM> good_res[MAX_OUTPUT_NUM+MAX_DFF_NUM];
void statistic(const string& name)
{
	initialization(name);
	//No fault circute
	simulate();
	copy(node_value,node_value+node_num,good_node_value);
	copy(res,res+res_length,good_res);
	//fault
	for(int i=0;i<gate_num;i++)
		{
		int p=cells[gate[i]].out;
		simulate(p,~good_node_value[p]);
		for(int j=0;j<output_num;j++)
			output_res[j]=res[j]^good_res[j];
		int count=0;
		for(int x=0;x<VEC_NUM;x++)
			{
			int y=0;
			while(y<output_num&&output_res[y][x]==0)
				y++;
			if(y<output_num)count++;
			}
		detectd[i][0]=count;
		for(int j=1;j<=dff_num;j++)
			detectd[i][j]=(res[j]^good_res[j]).count();
		}
	
	for(int i=0;i<dff_num;i++)
		{
		int p=cells[dff[i]].out;
		simulate(p,~good_node_value[p]);
		for(int j=0;j<output_num;j++)
			output_res[j]=res[j]^good_res[j];
		int count=0;
		for(int x=0;x<VEC_NUM;x++)
			{
			int y=0;
			while(y<output_num&&output_res[y][x]==0)
				y++;
			if(y<output_num)count++;
			}
		detectd[i+gate_num][0]=count;
		for(int j=1;j<=dff_num;j++)
			detectd[i+gate_num][j]=(res[j]^good_res[j]).count();
		}
//#if 0
	//print
cout<<"The value changed ratio(%):\n\
-----PO(output)--PPO(DFF)\n\
GATE   -----------------\n\
DFF     -----------------\n\n";
	int len=gate_num+dff_num;
	for(int i=0;i<len;i++)
		{
		if(i==gate_num)cout<<"\n";
		//PO(output)
		//int sum=0;
		//for(int j=0;j<output_num;j++)
			//sum+=detectd[i][j];
		//cout<<sum*100.0/VEC_NUM;
		//PPO(DFF)
		cout.precision(4);
		for(int k=0;k<=dff_num;k++)
			cout<<"\t"<<detectd[i][k]*100.0/VEC_NUM;
		cout<<"\n";
		}
//#endif
}
int main(int argc,char** argv)
{
	try{
		cout<<"Fault simulator 1.0\nAuthor L.Zhang 20130908\n";
		if(argc<2)throw msg("input parameter error");
		//ifstream in(argv[1]);
		//if(!in)throw msg(string(argv[1])+":cannot open");
		string name(argv[1]);
		//while(in>>name)
			//{
			clog<<name<<endl;
			statistic(name);
			//}
		//statistic("c17.bench");
		//statistic("s27.bench");
		//statistic("s208.1.bench");
		//statistic("s1488.bench");
	}
	
	//catch(regex_error e)
	//{
		//cout<<e.what()<<":"<<e.code()<<endl;
	//}
	catch(exception& e)
	{
		cerr<<e.what()<<endl;
	}
	catch(msg& e)
	{
		cerr<<e.what()<<endl;
	}
	cout<<"\n---\ntime used:"<<clock()<<endl;
	return 0;
}
